struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2)
{
    if (list1 == NULL)
    {
    	return list2;
    }
    if (list2 == NULL)
    {
    	return list1;
    }
    
    struct ListNode* merged = (struct ListNode*)malloc(sizeof(struct ListNode));
    merged->next = NULL;
    struct ListNode* tail = merged;
    
    while(list1 != NULL && list2 != NULL)
    {
        if(list1->data < list2->data)
        {
            tail->next = list1;
            list1 = list1->next;
        }
        else
        {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    if(list1 != NULL)
    {
        tail->next = list1;
    }
    if(list2 != NULL)
    {
        tail->next = list2;
    }

    return merged->next;
}